package com.kymatrix.kycarbon.xsmd.common.util;

import cn.hutool.core.collection.CollectionUtil;
import com.kymatrix.kycarbon.xsmd.common.constants.Constant;
import com.kymatrix.kycarbon.xsmd.common.exception.BusinessException;
import java.util.Iterator;
import java.util.List;
import java.util.function.Predicate;

/**
 * @author liujie
 * @date 2024-03-13
 */
public class TreeUtil {
    
    private TreeUtil() {
        throw new BusinessException(Constant.FAILED);
    }

    /**
     * 树形结构筛选
     */
    public static <T extends TreeNode> List<T> filter(List<T> list, Predicate<T> predicate) {
        if (predicate == null) {
            return list;
        }
        doFilter(list, predicate);
        return list;
    }

    private static <T extends TreeNode> void doFilter(List<T> list, Predicate<T> predicate) {
        Iterator<T> parent = list.iterator();
        while (parent.hasNext()) {
            //当前节点
            T t = parent.next();
            if (!predicate.test(t)) {
                //当前节点不包含关键字，继续遍历下一级
                // 取出下一级节点
                List<T> children = t.getChildrenList();
                // 递归
                if (!CollectionUtil.isEmpty(children)) {
                    doFilter(children, predicate);
                }
                //下一级节点都被移除了，那么父节点也移除，因为父节点也不包含关键字
                if (CollectionUtil.isEmpty(t.getChildrenList())) {
                    parent.remove();
                }
            } else {
                //当前节点包含关键字，继续递归遍历
                //子节点递归如果不包含关键字则会进入if分支被删除
                List<T> children = t.getChildrenList();
                // 递归
                if (!CollectionUtil.isEmpty(children)) {
                    doFilter(children, predicate);
                }
            }
        }
    }

}
